package hotLeetcode;

public class H79Leetcode {

    // 定义四个方向的增量数组，分别代表上、右、下、左
    private static final int[] rowDir = {-1, 0, 1, 0};
    private static final int[] colDir = {0, 1, 0, -1};

    public boolean exist(char[][] board, String word) {



        int rows = board.length;
        int cols = board[0].length;

        //遍历board 寻找与 word 第一个字符相匹配的位置
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;


    }

    private boolean dfs(char[][] board, String word, int row, int col, int index) {
        //如果已经匹配到单词的最后一个字符，则返回true
        if (index == word.length()) {
            return true;
        }

        //检查边界条件，当前字符是否匹配以及是否已访问过
        if (row < 0 || col < 0 || row >= board.length || col >= board[row].length || board[row][col] != word.charAt(index)) {
            return false;
        }

        //标记当前位置已访问
        char temp = board[row][col];
        board[row][col] = '#'; // 使用特殊字符标记，避免重复访问

        //尝试四个方向
        for (int i = 0; i < 4; ++i) {
            int newRow = row + rowDir[i];
            int newCol = col + colDir[i];

            if (dfs(board, word, newRow, newCol, index + 1)) {
                return true;
            }


        }

        // 回溯： 恢复当前位置的原始值
        board[row][col] = temp;



        return false;
    }


}
